一个可爱的 CDQ ,我们将原始序列看成一个一个加入,然后后面的操作就是一个一个删除,这么一个一个操作我们都记下来,然后每个操作记一个 id 表示它将为第几个时间点做出贡献。
当然对于原始序列的一个一个插入的操作这里的贡献是 1 ,删除操作的贡献自然是 −1 。
每个时间点统计答案,最后输出前做一个前缀和然后依次输出就好了。
这是具体的框架,但是统计 ans 数组具体怎么做呢?
可以知道对于一个位置 i ,位置上的元素是 ai 。对于一个 j 满足 j≤i ,并且 ai≤aj ,而且还要保证 idj≤idi ,那么 j 就可以对 i 做出贡献。这个就是在 i 前面的元素可以做出的贡献。i 后面的元素做出的贡献同理。
这就是一个很普通的三位偏序了,注意要开 long long 。
Code:
1 |
|
本文标题:【题解】 [CQOI2011]动态逆序对 CDQ分治 luoguP3157
文章作者:Qiuly
发布时间:2019年03月30日 - 00:00
最后更新:2019年03月30日 - 15:37
原始链接:http://qiulyblog.github.io/2019/03/30/[题解]luoguP3157/
许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。
v1.5.2